A term graph is a representation of an expression in a formal language as a generalized
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
whose vertices are .
Term graphs are a more powerful form of representation than expression trees because they can represent not only common subexpressions (i.e. they can take the structure of a directed acyclic graph) but also cyclic/recursive subexpressions (cyclic digraphs).
Abstract syntax trees are not capable of representing shared subexpressions since each tree node can only have one parent; this simplicity comes at a cost of efficiency due to redundant duplicate computations of identical terms. For this reason term graphs are often used as an
intermediate language
An intermediate representation (IR) is the data structure or code used internally by a compiler or virtual machine to represent source code. An IR is designed to be conducive to further processing, such as optimization and translation. A "good ...
at a subsequent compilation stage to abstract syntax tree construction via parsing.
The phrase "term graph rewriting" is often used when discussing graph rewriting methods for transforming expressions in formal languages.
Considered from the point of view of graph grammars, term graphs are not regular graphs, but hypergraphs where an n-ary word will have a particular subgraph in first place, another in second place, and so on, a distinction that does not exist in the usual undirected graphs studied in graph theory.
Term graphs are a prominent topic in programming language research since term graph rewriting rules are capable of formally expressing a compiler's
operational semantics
Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execu ...
. Term graphs are also used as abstract machines capable of modelling chemical and biological computations as well as graphical calculi such as concurrency models. Term graphs can perform automated verification and logical programming since they are well-suited to representing quantified statements in first order logic. Symbolic programming software is another application for term graphs, which are capable of representing and performing computation with abstract algebraic structures such as groups, fields and rings.
The TERMGRAPH conference focuses entirely on research into term graph rewriting and its applications.
Term graphs are also used in type inference, where the graph structure aids in implementing type unification.
[Fritz Henglein (1988)]
Type inference and semi-unification
In Proc. 1988 ACM conference on LISP and functional programming, pp. 184-197.
See also
*
Term (logic)
In mathematical logic, a term denotes a mathematical object while a formula denotes a mathematical fact. In particular, terms appear as components of a formula. This is analogous to natural language, where a noun phrase refers to an object and a w ...
*
Graph rewriting
In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also ...
References
Graph rewriting
Formal systems
Logical expressions
Graph data structures
{{formalmethods-stub